package BFS解决FloodFill算法;

import java.util.LinkedList;
import java.util.Queue;
//在一个二维数组中，从给定的起始位置开始，将与该位置相同颜色的相邻区域替换为新的颜色。
// 思路：首先来统计初始的颜色 prev  prev == color ? return image : 继续下一步
// 如果不是，就开始进行bfs进行依次访问所有相邻的子节点，只有子节点的颜色与根节点的初始颜色相同时方可添加到队列
// 添加后再根据子节点进行变色后，再访问字节点相邻的其他节点，直到队列为空
public class 图像渲染 {

    int [] dx = {0,0,1,-1};
    int [] dy = {1,-1,0,0};

    public int [][] floodFill(int [][] image, int sr,int sc,int color)
    {
        int prev = image[sr][sc]; // 统计刚开始的颜色

        if(prev == color) return image; //处理边界情况
        int m = image.length, n = image[0].length;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int []{sr,sc});
        while(!q.isEmpty())
        {
            int [] t = q.poll();
            int a = t[0], b = t[1];
            image[a][b] = color;
            for(int i = 0 ; i<4;i++)
            {
                int x = a+dx[i];
                int y = b+dy[i];
                if(x>=0 && x<m && y>=0 && y<n && image[x][y] == prev)
                {
                    q.add(new int []{x,y});
                }

            }
        }
        return image;
    }

}
